/**
 * 给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
 *
 * 每步 可以删除任意一个字符串中的一个字符。
 */
class MinDistanceCharacter {
    /**
     * 法一：正常动态规划
     * @param word1
     * @param word2
     * @return
     */
     public int minDistance(String word1, String word2) {
        int n=word1.length();
        int m=word2.length();
        int lsc=dp(word1,word2,n,m);
        return m-lsc+n-lsc;
    }
    
    public int dp(String word1,String word2,int n,int m) {
        int[][] dp=new int[n+1][m+1];
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                if(word1.charAt(i-1)==word2.charAt(j-1)) {
                    dp[i][j]=dp[i-1][j-1]+1;
                } else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n][m];
        
    }

    /**
     * 法二：递归版动态规划
     * @param word1
     * @param word2
     * @return
     */
    public int minDistanceDpMemo(String word1, String word2) {
        int n=word1.length();
        int m=word2.length();
        memo=new int[n][m];
        for(int[] row:memo) {
            Arrays.fill(row,-1);
        }
        int lsc=dpMemo(word1,0,word2,0);
        return n-lsc+m-lsc;
    }
    int[][] memo;
    public int dpMemo(String word1,int i,String word2,int j) {
        if(i==word1.length()||j==word2.length()) {
            return 0;
        }

        if(memo[i][j]!=-1) {
            return memo[i][j];
        }
        if(word1.charAt(i)==word2.charAt(j)) {//两个字母相等是公共子序列
            memo[i][j]=1+dpMemo(word1,i+1,word2,j+1);
        }
      else {
            memo[i][j]=Math.max(
                        dpMemo(word1,i+1,word2,j),//s1所指的这个字母没在公共子序列中
                        dpMemo(word1,i,word2,j+1)//s2所指的这个字母没在公共子序列中
            );
        }
        return memo[i][j];
    }
}